#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int E;

struct QNode {
    E element;
    struct QNode *next;
};

typedef struct QNode *Node;

struct Queue {
    Node front, rear;
};

typedef struct Queue *LinkedQueue;   //因为要存储首位两个指针，所以这里封装一个新的结构体吧

bool initQueue(LinkedQueue queue) {
    Node node = malloc(sizeof(struct QNode));
    if (node == NULL) return false;
    queue->rear = queue->front = node;
    return true;
}

bool offerQueue(LinkedQueue queue, E element) {
    Node node = malloc(sizeof(struct QNode));
    if (node == NULL) return false;
    node->element = element;
    queue->rear->next = node;
    queue->rear = node;
    return true;
}

bool isEmpty(LinkedQueue queue) {
    return queue -> rear == queue -> front;
}

E pollQueue(LinkedQueue queue) {
    Node tmp = queue->front->next;
    E element = tmp->element;
    queue->front->next = queue->front->next->next;
    if (queue->rear == tmp) queue->rear = queue->front;
    free(tmp);
    return element;
}

void printQueue(LinkedQueue queue) {
    printf("<<< ");
    Node node = queue->front->next;
    while (1) {    //注意不能直接判空，因为前面我们没考虑，也就没将新结点next设定为NULL
        printf("%d ", node->element);
        if (node == queue->rear) break;    //当已经打印最后一个元素后，再结束
        else node = node->next;
    }
    printf("<<<\n");
}

int main() {
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)){
        printf("%d ", pollQueue(&queue));
    }
    return 0;
}